#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;

//5.7.1 哈夫曼树的基本概念
//路径，结点的路径长度，树的路径长度(所有结点)TL，权(weight)，结点的带权路径长度
//树的带权路径长度 WPL（Weighted Path Length）：树中所有 叶子结点 的带权路径长度之和  
//结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树。 

//哈夫曼树：最优树。带权路径长度WPL最短的树 

//"带权路径长度最短" 是在"度相同"的树中比较而得的结果，因此有最优二叉树、最优三叉树之称

//最优二叉树：WPL最短的二叉树     
//满二叉树不一定是哈夫曼树 
//哈夫曼树中 权越大的叶子离根越近
//具有相同带权结点的哈夫曼树不唯一



//贪心算法：构造哈夫曼树时首先选择权值小的叶子结点 
//哈夫曼算法(构造哈夫曼树的方法)
//(1)构造森林全是根 
//(2)选用两小造新树 
//(3)删除两小添新人
//(4)重复(2)(3)剩单根 

//包含n个叶子结点的哈夫曼树中共有 2n - 1 个结点 ，度为2的结点(即n-1次合并后建立的结点)共有n-1个 
//哈夫曼树的结点的度数为 0 或 2，没有度为 1 的结点 

//哈夫曼树构造算法的实现
//采用顺序存储结构----一维结构数组 HuffmanTree H;
//***哈夫曼树中共有2n-1个结点，不使用0下标，数组大小为2n**** 
//结点类型定义
typedef struct {
	int weight; //结点的权值 
	int parent, lch, rch;
}HTNode, *HuffmanTree; 
//算法5.10 
void Select(HuffmanTree H, int n, int &s1, int &s2){
	int weight_s1 = 0,weight_s2 = 0;
	int i;
	for(int i = 1; i <= n; i++){
		if(H[i].parent == 0 && (H[i].weight < weight_s1 || weight_s1 == 0)){
			weight_s1 = H[i].weight;
			s1 = i;
		}
	}
	for(int i = 1; i <= n; i++){
		if(H[i].parent == 0 && i != s1 && (H[i].weight < weight_s2 || weight_s2 == 0) ){
			weight_s2 = H[i].weight;
			s2 = i;
		}
	}
	H[s1].parent = H[s2].parent = n + 1;
}

void CreateHuffmanTree(HuffmanTree &HT, int n){ //构造哈夫曼树----哈夫曼算法 
	if(n <= 1) return;
	int m = 2 * n - 1; //数组共有2n-1个元素 
	HT = new HTNode[m+1];// 0号单元未用，HT[m] 表示根节点 
	for(int i = 1; i <= m; i++){ //将2n-1个元素的lch、rch、parent置为0 
		HT[i].lch = 0;
		HT[i].rch = 0;
		HT[i].parent = 0;
	}
	for(int i = 1; i <= n; i++){
		cout<<"请输入第"<<i<<"个叶子结点的权值：";
		cin>>HT[i].weight; //输入前n个元素的weight值 
	}
	//初始化结束，下面开始建立哈夫曼树
	for(int i = n+1; i <= m; i++){ //合并产生n-1个结点----构造HuffmanTree 
		int s1 = 0, s2 = 0;
		Select(HT, i-1, *&s1, *&s2);  //在HT[k](1<=k<=i-1)中选择两个 其双亲域为0,且权值最小 的结点，并返回它们在HT中的序号s1和s2
		printf("s1 = %d, s2 = %d\n",s1, s2);
		HT[i].lch = s1, HT[i].rch = s2; //s1, s2分别作为i的左右孩子
		HT[i].weight = HT[s1].weight + HT[s2].weight; //i的权值为左右孩子权值之和 
	}
}



//前缀编码：任一字符的编码都不是另一字符的编码的 前缀
//哈夫曼编码：什么样的前缀码使得电文总长最短
//1.统计字符集中 每个字符在电文中出现的平均概率(概率越大，要求编码越短)
//2.利用哈夫曼树的特点：权越大的叶子离根越近；将每个字符的概率值作为权值，构造哈夫曼树。则概率越大的结点,路径越短 
//3.在哈夫曼树的每个分支上标上0或者1
//		 结点的左分支标0， 右分支标1 
//		把从根到每个叶子的路径上的标号连接起来，作为该叶子代表的 字符的编码 

//性质1：哈夫曼编码是前缀码 
//性质2：哈夫曼编码是最优前缀码  
typedef char *HuffmanCode; //动态分配数组，存储哈夫曼编码 
void CreateHuffmanCode(HuffmanTree HT, HuffmanCode *HC, int n){
	//从叶子到根逆向求每个字符的哈夫曼编码，存储在编码表HC中
	HC = new char *[n+1];  //分配n个字符编码的头指针矢量
	char *cd = new char[n];  //分配临时存放编码的动态数组空间 
	cd[n-1] = '\0'; //编码结束符
	for(int i = 1; i <= n; i++){  //逐个字符求哈夫曼编码 
		int start = n - 1;
		int c = i;
		int f = HT[i].parent;
		while( f != 0 ){ //从叶子结点开始向上回溯，直到根结点
			--start;  //回溯一次start向前指一个位置
			if(HT[f].lch == c) cd[start] = '0'; //结点c是f的左孩子，则生成代码0
			else cd[start] = '1';  //结点c是f的右孩子，则生成代码1
			c = f;
			f = HT[f].parent; //继续向上回溯 
		} //求出第i个字符的编码
		HC[i] = new char[n - start]; //为第i个字符串编码分配空间
		strcpy(HC[i], &cd[start]); //将求求得的编码从临时空间cd复制到HC的当前行中 
	}
	delete cd; //释放临时空间 
}




int main(void){
	HuffmanTree HT;
	//1-8的权值：5,29,7,8,14,23,3,11  创建完毕后的parent值：9,14,10,10,12,13,9,11 
	//创建完毕后，9-15
	//weight:8,15,19,29,42,58,100
	//parent:11,12,13,14,15,15,0
	//lch:7,3,9,5,11,2,1,13
	//rch:1,4,8,10,6,12,14 
	puts("请输入叶子结点个数：");
	int leaf_nodes;
	scanf("%d", &leaf_nodes);
	CreateHuffmanTree(HT, leaf_nodes);
	puts("HuffmanTree has been created!");
	for(int i = 1; i <= 2*leaf_nodes - 1; i++){
		printf("第%d个结点\tweight：%d\tparent：%d\tlch：%d\trch：%d\n", i, HT[i].weight, HT[i].parent, HT[i].lch, HT[i].rch);
	}
	return 0;
}